package datastructure.graph.最小生成树;

import datastructure.tree.BinaryHeap;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/28 9:42 上午
 */
public class LazyPrimMST {
    private BinaryHeap<Edge>pq;
    private Queue<Edge> mst;
    private boolean[] marked;

    public LazyPrimMST(EdgeWeightedGraph graph) {
        pq=new BinaryHeap<>();
        mst=new LinkedList<>();
        marked=new boolean[graph.V()];

        visit(graph,5);
        while (!pq.isEmpty()){
            Edge edge = pq.delMin();
            int v=edge.either(),w=edge.other(v);
            if (marked[v] && marked[w]){
                continue;
            }
            mst.add(edge);
            if (!marked[v]){
                visit(graph,v);
            }
            if (!marked[w]){
                visit(graph,w);
            }
        }
    }

    private void visit(EdgeWeightedGraph graph, int v) {
        marked[v]=true;
        for (Edge edge : graph.adj(v)) {
            int w = edge.other(v);
            if (!marked[w]){
                pq.insert(edge);
            }
        }
    }
    /**
     * 返回最小生成树的所有边
     * @return
     */
    public Iterable<Edge> edges(){
        return mst;
    }

    /**
     * 最小生成树的权重和
     * @return
     */
    public double weight(){
        double weight=0;
        for (Edge edge:mst){
            weight+=edge.weight();
        }
        return weight;
    }

    public static void main(String[] args) {


        EdgeWeightedGraph graph= new EdgeWeightedGraph(8);
        graph.addEdge(new Edge(4,5,0.35));
        graph.addEdge(new Edge(4,7,0.37));
        graph.addEdge(new Edge(5,7,0.28));
        graph.addEdge(new Edge(0,7,0.16));
        graph.addEdge(new Edge(1,5,0.32));
        graph.addEdge(new Edge(0,4,0.38));
        graph.addEdge(new Edge(2,3,0.17));
        graph.addEdge(new Edge(1,7,0.19));
        graph.addEdge(new Edge(0,2,0.26));
        graph.addEdge(new Edge(1,2,0.36));
        graph.addEdge(new Edge(1,3,0.29));
        graph.addEdge(new Edge(2,7,0.34));
        graph.addEdge(new Edge(6,2,0.40));
        graph.addEdge(new Edge(3,6,0.52));
        graph.addEdge(new Edge(6,0,0.58));
        graph.addEdge(new Edge(6,4,0.93));
        LazyPrimMST mst = new LazyPrimMST(graph);
        for (Edge e : mst.edges()) {
            System.out.println(e);
        }
        System.out.println(mst.weight());
    }
}

